import heapq
from typing import List


class Solution:
    def processTasks(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda x: x[0])  # 按开始时间排序任务列表
        tasks.append([10 ** 9, 10 ** 9, 1])  # 添加哨兵任务

        ans = 0
        heap = []  # heap[i] = [任务最晚启动时间]

        for start, end, period in tasks:
            while heap and heap[0][0] + ans < start:
                if heap[0][0] + ans >= heap[0][1]:
                    heapq.heappop(heap)  # 任务已经被完成了
                else:
                    ans += min(heap[0][1], start) - heap[0][0] - ans  # 运行到当前时间或运行到任务结束
            heapq.heappush(heap, [end - period + 1 - ans, end + 1])  # 当前之前的运行时间是无效的，所以减去ans
        return ans


if __name__ == "__main__":
    print(Solution().processTasks(tasks=[[1, 3, 2], [2, 5, 3], [5, 6, 2]]))  # 4
    print(Solution().processTasks(tasks=[[2, 3, 1], [5, 5, 1], [5, 6, 2]]))  # 3

    # 测试用例8 : 54
    print(Solution().processTasks(
        tasks=[[10, 42, 6], [47, 81, 35], [38, 58, 13], [39, 48, 4], [12, 62, 24], [54, 73, 1], [59, 96, 34],
               [65, 91, 20]]))
